googologywikiaorg-20200223-history
User blog:QuasarBooster/Higher order worms?
I haven't seen anything like this on the site yet so I'll share some ideas. I apologise for the post being so long. Beklemishev/First-order worms Here is a reminder of how to attack basic worms, which I'll call "first-order" worms. The following rules apply while the worm is still alive (i.e. the list still contains numbers). At turn k'' of the battle, *If the last entry is 0, then remove it from the list. *Otherwise, locate the rightmost entry whose value is less than the last entry. Let the bad part of the list be all entries to the right of that entry. If such an entry doesn't exist, let the bad part be the entire list. Decrease the last entry by one, then add ''k copies (or k''+1 depending on how you count) of the bad part to the end of the list. As you know, it has been proven that any worm can be killed in a finite number of turns. The function \(\text{Worm}(n)\) denotes the number of turns required before the worm n is killed. You also know that this function is comparable to \(f_{\varepsilon_0}(n)\). Second-order worms Here's where there's interesting potential. Define a second-order worm as a list of first-order worms. Then the previous rules could be adjusted to work on second-order worms until they're dead (i.e. empty lists). At turn ''k of the battle, *If the last entry is a dead worm, then remove it from the list. *Otherwise, locate the rightmost entry that lexicographically comes before the last entry (I'll explain this shortly). Let the bad part of the list be all entries to the right of that entry. If such an entry doesn't exist, let the bad part be the entire list. Attack the last entry worm as if it were on turn k'', then add ''k copies (or k''+1 depending on how you count) of the bad part to the end of the list. Lexicographic ordering refers to how, for example, words are sorted in a dictionary. *Aardvark < Arkansas < Arkansasssss The same logic works for lists of numbers and can be used to compare first-order worms. *3,4,4,0,1 < 3,4,5,0,1 < 3,4,5,0,1,1,1 The big question now is whether or not any second-order worm can also be killed in a finite number of turns. I highly suspect that it can, on the basis that any first-order worm eventually "decreases" to an empty list just like how any entry in a first-order worm eventually decreases to 0. If we assume that they do eventually die, then we can denote as \(\text{Worm}_2(n)\) the number of turns required before the second-order worm [ n ] is killed. Higher-order worms It's not hard to continue this idea, defining an order ''N+1 worm as a list of order N worms. The great thing is that lists containing other lists can still be lexicographically ordered, meaning that the rules for second-order worms could be inductively extended for all higher orders. Again, I can only conjecture that these "hyper-worms" all eventually terminate. I suspect that, if one can prove that all order 2 worms die, then it wouldn't be very different to prove that higher orders also die. If that is the case, then we can denote by \(\text{Wormception}(n)=\text{Worm}_n(n)\) the number of turns required before the order-n worm [[...n...]] is killed. I can't help but wonder what such a function's growth rate is, assuming it exists. Examples Wormception(0) = 0 (no list is actually made) Wormception(1) = 3 *1 *0,0 *0 *[] Wormception(2)... *[ 2 ] *[1,1,1,1] *[1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0] Wormception(3)... *[3] *[[2, 2], [2, 2]] *[[2, 2], [2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1], [2, 2], [2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1], [2, 2], [2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1]] Category:Blog posts